package com.lsa.letcode.the114.flattenBtToLinkedList;

import com.lsa.letcode.common.TreeNode;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
    	doFlatten(root);
    }
    
    private Pair doFlatten(TreeNode r) {
    	if (r != null){
    		Pair leftRes = doFlatten(r.left);
    		Pair rightRes = doFlatten(r.right);
    		return concat(leftRes, r, rightRes);
    	}
    	else {
    		return null;
    	}
    }
    
    private static Pair concat(Pair p1, TreeNode r, Pair p2) {
    	r.left = null;
    	if (p1 == null && p2 == null){
    		return new Pair(r, r);
    	}
    	else if (p1 == null){
    		r.right = p2.first;
    		return new Pair(r, p2.last);
    	}
    	else if (p2 == null){
    		r.right = p1.first;
    		return new Pair(r, p1.last);
    	}
    	r.right = p1.first;
    	p1.last.right = p2.first;
    	return new Pair(r, p2.last);
    }
    
    static class Pair{
    	TreeNode first;
    	TreeNode last;
    	
		Pair(TreeNode first, TreeNode last) {
			this.first = first;
			this.last = last;
		}
		
		Pair() {
		}
    }
}